package shiyan1;

/**
 * Created by zhangyunqi on 2017/6/7.
 */

 import java.*;

public class MyBC{
    public static String toPostfix(String expr){
        MyStack<String> stack = new MyStack<>(expr.length());
        String postfix = "";
        int i = 0;
        while(i<expr.length()){
            char ch = expr.charAt(i);
            switch (ch){
                case  '+':
                case  '-':while(!stack.isEmpty() && !stack.get().equals("("))
                    postfix += stack.pop();
                    //postfix += " ";
                    stack.push(ch + "");
                    i++;
                    break;
                case '*':
                case '/':while (!stack.isEmpty() && (stack.get().equals("*")||stack.get().equals("/")))
                    postfix += stack.pop();
                    //postfix += " ";
                    stack.push(ch + "");
                    i++;
                    break;
                case '(':stack.push(ch + "");
                    i++;
                    break;
                case ')':String out = stack.pop();
                    while(out!=null && !out.equals("(")){
                        postfix += out;
                        out = stack.pop();
                        //postfix += " ";
                    }
                    i++;
                    break;
                default:while(i < expr.length() && ch>='0' && ch<='9'){
                    postfix += ch;
                    i++;
                    if(i<expr.length())
                        ch = expr.charAt(i);
                }
                    postfix += " ";
            }
        }
        while (!stack.isEmpty())
            postfix += stack.pop();
        return postfix;
    }



    public interface SStack<T> {
        boolean isEmpty();
        void push(T x);
        T pop();
        T get();
    }
    public static class MyStack<T> implements SStack<T> {
        private Object element[];
        private int top;
        public MyStack(int size){
            this.element = new Object[Math.abs(size)];
            this.top = -1;
        }
        public MyStack() {
            this(64);
        }
        public boolean isEmpty() {
            return this.top == -1;
        }
        public void push(T x) {
            if(x==null)
                return;
            if(this.top == element.length-1){
                Object[] temp = this.element;
                this.element = new Object[temp.length*2];
                for(int i = 0; i < temp.length; i++)
                    this.element[i] = temp[i];
            }
            this.top++;
            this.element[this.top] = x;
        }
        public T pop() {
            return this.top==-1 ? null:(T)this.element[this.top--];
        }
        public T get() {
            return this.top==-1 ? null:(T)this.element[this.top];
        }
    }

}
